package interview.tree;

import algorithm.model.TreeNode;

/**
 * Leetcode 437
 * 路径求和3
 *
 * 给定一个二叉树和 目标和sum。找到这个二叉树中路径和为sum的总路径数。
 * 注意：路径不一定以root为起点，也不一定以叶子节点为终点，仅要求顺序是由上到下即可。
 *
 * 假设 path(n,sum) 是以n为根几点，和为sum的路径数
 * 那么：pathSum(n,sum) = path(n,sum) + path(n.left,sum) + path(n.right,sum)
 *
 * Created by yzy on 2021-02-07 15:49
 */
public class PathSumIII {


    /**
     * 双重递归，不是效率最好的。因为有重复计算
     * 可以增加一个列表，记录计算的结果
     * @param root
     * @param sum
     * @return
     */
    public int pathSum(TreeNode root, int sum) {
        if(root==null) return 0;
        return nodePathSum(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
    }

    private int nodePathSum(TreeNode node, int sum){
        if(node==null) return 0;

        // 注意。如果找到和了，还可能继续往下有延长的数目。比如 +2 -2 这样的。
        int res = 0;
        if(node.val == sum){
            res = 1;
        }
        return res + nodePathSum(node.left, sum-node.val) + nodePathSum(node.right, sum-node.val);
    }
}
